package srcInterviewPrep;

public final class SortedListToBSTConverter
{
    public static BTNode ConvertListToBST(LinkedListNode head)
    {
        int len = 0;
        LinkedListNode n = head;
        while (n != null)
        {
            n = n.next;
            ++len;
        }
        
        return ConvertListToBSTRecursively(head, len).btNode;
    }
    
    private static BTNode ConvertListToBST(LinkedListNode head, int len)
    {
        return ConvertListToBSTRecursively(head, len).btNode;
    }
    
    private static Pair ConvertListToBSTRecursively(
        LinkedListNode linkedListNode,
        int len)
    {
        if (len <= 0)
        {
            return new Pair(null, linkedListNode);
        }
    
        int mid = len / 2;
        Pair p1 = ConvertListToBSTRecursively(linkedListNode, mid);
        
        BTNode btNode = new BTNode(p1.linkedListNode.data);
        btNode.left = p1.btNode;
        
        Pair p2 = ConvertListToBSTRecursively(p1.linkedListNode.next, len - mid - 1);
        btNode.right = p2.btNode;
        
        return new Pair(btNode, p2.linkedListNode);
    }
    
    private static final class Pair
    {
        BTNode btNode;
        LinkedListNode linkedListNode;
        
        private Pair(BTNode btNode, LinkedListNode linkedListNode)
        {
            this.btNode = btNode;
            this.linkedListNode = linkedListNode;
        }
    }
}

